Online Algorithms for Information Aggregation from Distributed and Correlated Sources

摘要

There is a fundamental trade-off between the communication cost and latencyin information aggregation. Aggregating multiple communication messages overtime can alleviate overhead and improve energy efficiency on one hand, butinevitably incurs information delay on the other hand. In the presence ofuncertain future inputs, this trade-off should be balanced in an online manner,which is studied by the classical dynamic TCP ACK problem for a singleinformation source. In this paper, we extend dynamic TCP ACK problem to ageneral setting of collecting aggregate information from distributed andcorrelated information sources. In this model, distributed sources observecorrelated events, whereas only a small number of reports are required from thesources. The sources make online decisions about their reporting operations ina distributed manner without prior knowledge of the local observations atothers. Our problem captures a wide range of applications, such as in-situsensing, anycast acknowledgement and distributed caching. We present simplethreshold-based competitive distributed online algorithms under differentsettings of intercommunication. Our algorithms match the theoretical lowerbounds in order of magnitude. We observe that our algorithms can producesatisfactory performance in simulations and practical testbed.